/*
 * @lc app=leetcode.cn id=295 lang=cpp
 *
 * [295] 数据流的中位数
 */

// @lc code=start
class MedianFinder
{
public:
  priority_queue<int, vector<int>, less<int>> left;    // 记录数据左边，大顶
  priority_queue<int, vector<int>, greater<int>> right;// 记录数据右边，小顶

  /** initialize your data structure here. */
  MedianFinder()
      : left(priority_queue<int, vector<int>, less<int>>())
      , right(priority_queue<int, vector<int>, greater<int>>())
  {}

  // 令 left.size() >= right.size()
  void addNum(int num)
  {
    // 添加到左边,从右边筛选出最小值并加入左边
    if (left.size() == right.size()) {
      right.push(num);
      left.push(right.top());
      right.pop();
    }
    // 添加到右边，从左边筛选出最大值并加入右边
    else {
      left.push(num);
      right.push(left.top());
      left.pop();
    }
  }

  double findMedian()
  {
    if (left.size() != right.size())
      return left.top();
    else
      return (left.top() + right.top()) / 2.0;
  }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */
// @lc code=end
